package leetcode_day._2021._202107._0110;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/7/9 14:34
 * 主要元素
 * 算法：数组   摩尔投票
 * 两次遍历数组
 * 第一次遍历找出重复最多的数字，
 * 第二次遍历看这个数字的次数是否是数组长度的一半
 * 如果两个数字不同，就抵消掉
 */
public class _09_面试题17_10 {

    public int majorityElement(int[] nums) {
        int x = -1, cnt = 0;
        for (int num : nums) {
            if (cnt == 0) {
                x = num;
                cnt = 1;
            }
            else cnt += x == num ? 1 : -1;
        }
        cnt = 0;
        for (int num : nums) {
            if (x == num) ++cnt;
        }
        return cnt > nums.length / 2 ? x : -1;
    }

}
